/*
 * @lc app=leetcode.cn id=1373 lang=typescript
 *
 * [1373] 二叉搜索子树的最大键值和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

//  思路：后序遍历
//  为了得到结果需要知道：
//  1、左右子树是否是 BST。
//  2、左子树的最大值和右子树的最小值。
//  3、左右子树的节点值之和。
//  因此在遍历时记录是否为BST、最小值、最大值和节点和
//  采用后序遍历，因为当前节点要做的事情需要通过左右子树的计算结果推导出来
//  参考：https://labuladong.github.io/algo/2/19/28/

function maxSumBST(root: TreeNode | null): number {
    let maxSum = 0
    interface Treeinfo {
        isBST: boolean
        min: number
        max: number
        sum: number
    }

    const traverse = (root: TreeNode | null): Treeinfo => {
        // basecase
        if (!root) {
            return {
                isBST: true,
                min: Infinity,
                max: -Infinity,
                sum: 0
            }
        }

        // 遍历左右子树
        const left: Treeinfo = traverse(root.left)
        const right: Treeinfo = traverse(root.right)
        let res: Treeinfo = {
            isBST: true,
            min: Infinity,
            max: -Infinity,
            sum: 0
        }

        // 当左右节点是BST、满足左小右大使得当前构成BST更新结果
        if (left.isBST && right.isBST && root.val > left.max && root.val < right.min) {
            res.isBST = true
            res.min = Math.min(left.min, root.val)
            res.max = Math.max(right.max, root.val)
            res.sum = left.sum + right.sum + root.val
            maxSum = Math.max(maxSum, res.sum)
        } else {
            res.isBST = false
        }
        return res
    }

    traverse(root)
    return maxSum
};
// @lc code=end

import { TreeNode } from "./type"
const root = TreeNode.buildTree([4, 3, null, 1, 2])
console.log(maxSumBST(root))
